package graph

func canFinish(numCourses int, prerequisites [][]int) bool {
	// 广度优先搜索
	// 顺序地生成拓扑排序，考虑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何先修课程。如果某个相邻的节点
	// 变成了 [没有任何入边的节点]，那么就代表这门课可以开始学习了。
	// 按照这样的流程，不断将没有入边的节点加入到答案，直到答案中包含所有的节点或者不存在没有入边的节点
	// 使用一个队列来进行bfs，初始时，所有入度为0的节点都被放入队列中，他们就是拓扑排序最前面的节点
	degree := make([]int, numCourses) // 入度数组
	edges := make([][]int, numCourses)
	res := []int{}

	// prerequisites : [[1, 0]] 代表学习1之前，需要学习0，那么 0 -> 1
	for _, info := range prerequisites {
		edges[info[1]] = append(edges[info[1]], info[0])
		degree[info[0]]++
	}
	
	q := []int{}
	for i := 0; i < numCourses; i++ {
		if degree[i] == 0 {
			q = append(q, i)
		}
	}

	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		res = append(res, u)
		for _, v := range edges[u] {
			degree[v]--
			if degree[v] == 0 {
				q = append(q, v)
			}
		}
	}

	return len(res) == numCourses
}